In [ ]:
%%HTML
<style>
.container { width:100% !important }
</style>
The function search
takes three arguments to solve a search problem:
start
is the start state of the search problem,goal
is the goal state, andnext_states
is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states.
For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
If successful, search
returns a path from start
to goal
that is a solution of the search problem
$$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$
In [ ]:
def search(start, goal, next_states):
Frontier = { start }
Visited = set()
Parent = { start: start }
while len(Frontier) > 0:
NewFrontier = set()
for s in Frontier:
for ns in next_states(s):
if ns not in Visited and ns not in Frontier:
NewFrontier.add(ns)
Parent[ns] = s
if ns == goal:
return path_to(goal, Parent)
Visited |= Frontier
Frontier = NewFrontier
Given a state
and a parent dictionary Parent
, the function path_to
returns a path leading to the given state
.
In [ ]:
def path_to(state, Parent):
p = Parent.get(state)
if p == state:
return [state]
return path_to(p, Parent) + [state]
Below, we ensure that we only import graphviz
if this notebook is not loaded from another notebook. This works by checking that the variable file
is not set.
In [ ]:
import graphviz as gv
The function $\texttt{toDot}(\texttt{source}, \texttt{Edges}, \texttt{Fringe}, \texttt{Visited})$ takes a graph that is represented by
its Edges
, a set of nodes Fringe
, and set Visited
of nodes that have already been visited.
In [ ]:
def toDot(source, goal, Edges, Frontier, Visited, Parent=None):
V = set()
for x, L in Edges.items():
V.add(x)
for y in L:
V.add(y)
dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
dot.attr(rankdir='LR', size='8,5')
for x in V:
if x == source:
dot.node(str(x), color='blue', shape='doublecircle')
elif x in Frontier and x == goal:
dot.node(str(x), label=str(x), color='magenta')
elif x in Frontier:
dot.node(str(x), label=str(x), color='red')
elif x in Visited:
dot.node(str(x), label=str(x), color='blue')
else:
dot.node(str(x), label=str(x))
if Parent:
Path = path_to(goal, Parent)
for u in V:
if Edges.get(u):
for v in Edges[u]:
if Parent and v in Path and Parent[v] == u:
dot.edge(str(u), str(v), color='brown', style='bold')
else:
dot.edge(str(u), str(v))
return dot
In [ ]:
def next_states_test(node):
x, y = node
return { (x+1, y), (x, y+1) }
In [ ]:
def create_edges(n):
Edges = {}
for row in range(n):
for col in range(n):
if (row, col) != (n-1, n-1):
Edges[(row, col)] = list(next_states_test((row, col)))
for k in range(n-1):
Edges[(k, n-1)] = [(k+1, n-1)]
Edges[(n-1, k)] = [(n-1, k+1)]
return Edges
In [ ]:
def search_show(start, goal, next_states, Edges):
Visited = set()
Frontier = { start }
Parent = { start: start }
while len(Frontier) > 0:
display(toDot(start, goal, Edges, Frontier, Visited))
NewFrontier = set()
Visited |= Frontier
for s in Frontier:
for ns in next_states(s):
if not (ns in Visited):
NewFrontier.add(ns)
Parent[ns] = s
if ns == goal:
display(toDot(start, goal, Edges, NewFrontier, Visited, Parent))
return
Frontier = NewFrontier
In [ ]:
def main(n):
Edges = create_edges(n)
search_show((0,0), (n-1,n-1), next_states_test, Edges)
In [ ]:
main(9)
In [ ]:
%run Missionaries.ipynb
In [ ]:
start = (3, 3, 1)
goal = (0, 0, 0)
In [ ]:
dot_graph(createRelation(start))
In [ ]:
%%time
Path = search(start, goal, nextStates)
printPath(Path)
The magic command %run
can be used to import the code of another notebook.
In [ ]:
%run Sliding-Puzzle.ipynb
In [ ]:
%%time
Path = search(start, goal, next_states)
print(len(Path)-1)
In [ ]:
animation(Path)